package _binary_tree

import common.v1.Node
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/description/

559. N 叉树的最大深度
    给定一个 N 叉树，找到其最大深度。
    最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
    N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

    示例 1：
    输入：root = [1,null,3,2,4,null,5,6]
    输出：3

    示例 2：
    输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
    输出：5
 */
class leetcode_559 {
    @Test
    fun test_1() {
        val root = Node(1)
        val n2 = Node(2)
        val n3 = Node(3)
        val n4 = Node(4)
        val n5 = Node(5)
        val n6 = Node(6)
        root.children = arrayListOf(n3, n2, n4)
        n3.children = arrayListOf(n5, n6)
        val actual = maxDepth(root)
        val expect = 3
        Assert.assertEquals(expect, actual)
    }


    @Test
    fun test_2() {
        val root = Node(1)
        val n2 = Node(2)
        val n3 = Node(3)
        val n4 = Node(4)
        val n5 = Node(5)
        val n6 = Node(6)
        val n7 = Node(7)
        val n8 = Node(8)
        val n9 = Node(9)
        val n10 = Node(10)
        val n11 = Node(11)
        val n12 = Node(12)
        val n13 = Node(13)
        val n14 = Node(14)
        root.children = arrayListOf(n2, n3, n4, n5)
        n3.children = arrayListOf(n6, n7)
        n4.children = arrayListOf(n8)
        n5.children = arrayListOf(n9, n10)
        n7.children = arrayListOf(n11)
        n8.children = arrayListOf(n12)
        n9.children = arrayListOf(n13)
        n11.children = arrayListOf(n14)

        val actual = maxDepth(root)
        val expect = 5
        Assert.assertEquals(expect, actual)
    }

    private fun maxDepth(root: Node?): Int {
        // return maxDepth1(root)
        return maxDepth2(root)
        // return maxDepth3(root)
    }

    private fun maxDepth1(root: Node?): Int {
        // 广度遍历
        // S - N
        // T - N
        if (null == root) {
            return 0
        }
        val queue: LinkedList<Node> = LinkedList<Node>()
        queue.offer(root)
        var depth: Int = 0
        while (!queue.isEmpty()) {
            depth++
            var size = queue.size
            while (size-- > 0) {
                val node = queue.poll()
                for (i in 0..node.children.size - 1) {
                    node.children.get(i).let { queue.offer(it) }
                }
            }
        }
        return depth
    }

    private fun maxDepth2(root: Node?): Int {
        // 深度搜索 - 前置遍历，求深度
        if (root == null) {
            return 0
        }
        getHeght(root, 1)
        return maxDeepth
    }

    var maxDeepth: Int = 0
    private fun getHeght(root: Node?, currnetDepth: Int) {
        if (root == null) {
            return
        }
        // 中
        maxDeepth = Math.max(currnetDepth, maxDeepth)
        // 左
        // 右
        var depth: Int = currnetDepth
        for (child in root.children) {
            if (child != null) {
                depth++
                getHeght(child, depth)
                depth--
            }
        }
    }

    fun maxDepth4(root: Node?): Int {
        collect(root, 0)
        return max
    }
    private var max: Int = 0
    fun collect(root: Node?, depth: Int) {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (null == root) {
            return
        }
        max = Math.max(depth + 1, max)
        // 3 确定单层递归的处理逻辑
        for (child in root.children) {
            child?.let {
                collect(it, depth + 1)
            }
        }
    }

    private fun maxDepth3(root: Node?): Int {
        // 深度搜索 - 后置遍历，求高度。高度和深度数值相同
        return getHeight(root)
    }

    private fun getHeight(root: Node?): Int {
        if (null == root) {
            return 0
        }
        // N （等价于二叉树 左、右）
        var maxChildHeight: Int = 0
        for (child in root.children) {
            maxChildHeight = Math.max(maxChildHeight, getHeight(child))
        }
        // 中
        val maxHeight: Int = maxChildHeight + 1
        return maxHeight
    }
}